package cn.jdemo.algorithm.demo;

import java.util.Arrays;

/**
 * 归并排序
 */
public class Demo03 {
    public static void main(String[] args) {
        mergeSort();
    }

    public static void mergeSort(){
        int[] arrs = new int[]{1,2,3,6,4,5,7,8,9,10,10};
        doMergeSort(arrs,0, arrs.length-1);
        System.out.println(Arrays.toString(arrs));
    }
    public static void doMergeSort(int[] arrs,int left, int right){
        if (left >= right ){
            return;
        }
        int mid = (right - left)/2 + left;
        doMergeSort(arrs,left,mid);
        doMergeSort(arrs,mid+1,right);
        merge(arrs,left,mid,right);
    }

    private static void merge(int[] arrs, int left, int mid,int right) {
        int[] tmp  = new int[arrs.length];
        for (int i = left; i <=right ; i++) {
            tmp[i] = arrs[i];
        }
        int idx1 = left;
        int idx2 = mid+1;

        for (int i = left; i <=right ; i++) {
            if (idx1 == mid+1){
                arrs[i] = tmp[idx2];
                idx2++;
                continue;
            }
            if (idx2 == right+1){
                arrs[i] = tmp[idx1];
                idx1++;
                continue;
            }
            if (tmp[idx1] <= tmp[idx2]){
                arrs[i] = tmp[idx1];
                idx1++;
                continue;
            }
            if (tmp[idx1] > tmp[idx2]){
                arrs[i] = tmp[idx2];
                idx2++;
                continue;
            }
        }
    }

    private static void swap(int[] arrs, int x, int y) {
        if (x == y){
            return;
        }
        arrs[x] = arrs[x] ^ arrs[y];
        arrs[y] = arrs[x] ^ arrs[y];
        arrs[x] = arrs[x] ^ arrs[y];
    }
}
